package lc;
import java.util.*;
import org.junit.*;

import util.BracketUtils;
public class Ex310 {
    class Solution {
        //先找出度为1的节点删除，最终剩下的就是根节点
        //注意：此为无向图，因此度是平等的，即只要存在边[i,j], 那么i和j都多了一个度
        public List<Integer> findMinHeightTrees(int n, int[][] edges) {
            if (n == 1) {
                return new ArrayList<>();
            }
            Map<Integer, Queue<Integer>> map = new HashMap<>(); //反向邻接表
            int[] dig = new int[n]; //度数
            //双向计算邻接表
            for (int[] edge: edges) {
                Queue<Integer> cur;
                if ((cur = map.get(edge[0])) == null) {
                    Queue<Integer> q = new ArrayDeque<>(){{offer(edge[1]);}};
                    map.put(edge[0], q);
                } else {
                    cur.offer(edge[0]);
                }
                if ((cur = map.get(edge[1])) == null) {
                    Queue<Integer> q = new ArrayDeque<>(){{offer(edge[0]);}};
                    map.put(edge[1], q);
                } else {
                    cur.offer(edge[1]);
                }
                dig[edge[0]]++;
                dig[edge[1]]++;
            }
            Queue<Integer> queue = new ArrayDeque<>();
            int cnt = n; //度大于1的节点的计数
            for (int i = 0; i < n; i++) {
                if (dig[i] == 1) {
                    queue.offer(i); //边缘节点率先出栈。
                    cnt--;
                }  
            }
            while (cnt > 0) {
                int cur = queue.poll();
                //将边缘节点相邻的节点的度降低1个
                Queue<Integer> q = map.remove(cur);
                while (!q.isEmpty()) {
                    int p = q.poll();
                    dig[p]--;
                    if (dig[p] == 1) {
                        queue.offer(p);
                        cnt--;
                    }
                }
            }
            return new ArrayList<>(queue);
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[][] nums = BracketUtils.to2DArray("[[1,0],[1,2],[1,3]]");
        System.out.println(s.findMinHeightTrees(4, nums));
    }
}
